#define _CRT_SECURE_NO_WARNINGS 1


//#include<vector>
//#include<iostream>
//
//using namespace std;
//
//vector<int> searchRange(vector<int>& nums, int target)
//{
//    vector<int> v(2, -1);
//    int left = 0, right = nums.size() - 1, mid = 0;
//    while (left < right)
//    {
//        mid = left + (right - left) / 2;
//        if (nums[mid] < target)
//        {
//            left = mid + 1;
//        }
//        else
//        {
//            right = mid;
//        }
//    }
//    if (nums[left] == target)
//    {
//        v[0] = left;
//    }
//    left = 0, right = nums.size() - 1, mid = 0;
//    while (left < right)
//    {
//        mid = left + (right - left + 1) / 2;
//        if (nums[mid] <= target)
//        {
//            left = mid;
//        }
//        else
//        {
//            right = mid - 1;
//        }
//    }
//    v[1] = right;
//    return v;
//}
//
//int main()
//{
//    vector<int> v = { 5,7,7,8,8,10 };
//    vector<int> ret = searchRange(v, 6);
//    for (auto& e : ret)
//    {
//        cout << e << ' ';
//    }
//    cout << endl;
//
//	return 0;
//}


#include<vector>
#include<iostream>

using namespace std;

int mySqrt(int x)
{
    vector<int> v;
    v.push_back(1);
    for (int i = 0; v[i] <= x; i++)
    {
        int val = i + 2;
        v.push_back(val * val);
    }
    int left = 0, right = v.size() - 1;
    while (left < right)
    {
        int mid = left + (right - left) / 2;
        if (v[mid] < x)
        {
            left = mid + 1;
        }
        else
        {
            right = mid;
        }
    }
    return left;
}

int main()
{
    cout << mySqrt(4) << endl;

	return 0;
}